package com.ma.tree;

import java.io.PushbackInputStream;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.ArrayBlockingQueue;

public class BinaryTree {




    //TODO  递归序
    /**
     * 先序遍历
     * @param head
     */
    public static void pre(Node head){
        if(head==null){
            return;
        }
        System.out.println(head.value);
        pre(head.left);
        pre(head.right);

    }


    /**
     * 中序遍历
     * @param head
     */
    public static void in(Node head){
        if(head==null){
            return;
        }
        in(head.left);
        System.out.println(head.value);
        in(head.right);
    }

    /**
     * 后序遍历
     * @param head
     */
    public static void pos(Node head){
        if(head==null){
            return;
        }
        pos(head.left);
        pos(head.right);
        System.out.println(head.value);

    }



    //TODO 非递归

    /**
     * 先序遍历非递归
     * @param head
     */
    public static void preNoRecursive(Node head){
        System.out.println("先序遍历:");
        if(head!=null){
            Stack<Node> stack=new Stack<>();
            stack.add(head);
            while (!stack.isEmpty()){
                head=stack.pop();
                System.out.print(head.value+",");
                if(head.left!=null){
                    stack.push(head.left);
                }
                if(head.right!=null){
                    stack.push(head.right);
                }
            }
        }
        System.out.println(";over!");
    }

    /**
     * 后序遍历非递归
     * @param head
     */
    public static void posNoRecursive(Node head){
        System.out.println("后序遍历:");
        if(head!=null){
            Stack<Node> stack=new Stack<>();
            Stack<Node> s=new Stack<>();
            stack.add(head);
            while (!stack.isEmpty()){
                head=stack.pop();
                s.push(head);
                if(head.left!=null){
                    stack.push(head.left);
                }
                if(head.right!=null){
                    stack.push(head.right);
                }
            }
            while (!s.isEmpty()){
                System.out.println(s.pop().value+", ");
            }
        }
        System.out.println(";over!");
    }


    /**
     * 中序遍历非递归
     * @param head
     */
    public static  void inNoRecursive(Node head){
        System.out.println("中序遍历:");
        if(head!=null){
            Stack<Node> stack=new Stack<>();
            while (!stack.isEmpty()||head!=null){
                if(head!=null){
                    stack.push(head);
                    head=head.left;

                }else {
                    head=stack.pop();
                    System.out.println(head.value+",");
                    head=head.right;
                }
            }


        }
        System.out.println(";over!");


    }


    /**
     * 中序遍历非递归方法2
     * @param head
     */
    public static void inNoRecursive2(Node head){
        System.out.println("中序遍历2:");
        if(head!=null){
            Stack<Node> stack=new Stack<>();
            stack.push(head);
            Node c=null;
            while (!stack.isEmpty()){
                c=stack.peek();
                if(c.left!=null&&head!=c.left&&head!=c.right){
                    stack.push(c.left);
                }else if(c.right!=null&& head!=c.right){
                    stack.push(c.right);
                }else {
                    System.out.println(stack.pop().value+",");
                    head=c;
                }
            }
        }
        System.out.println(";over!");

    }


    /**
     * 二叉树按层遍历
     * @param head
     */
    public static void level(Node head){
        if(head==null){
            return;
        }
        Queue<Node> queue =new LinkedList<>();


        queue.add(head);
        while (!queue.isEmpty()){
            Node cur=queue.poll();
            System.out.println(cur.value+" ");
            if(cur.left!=null){
                queue.add(cur.left);
            }
            if(cur.right!=null){
                queue.add(cur.right);
            }
        }
    }


    /**
     * 利用map求最大宽度
     * @param head
     * @return
     */
    public static  int maxWidthUseMap(Node head){
        if(head==null){
            return 0;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        HashMap<Node,Integer> levelMap = new HashMap<>();
        levelMap.put(head,1);
        int curLevel=1;//当前节点层
        int curLevelNodes=0;//当前层的节点数量
        int max=0;//最大节点数
        while (!queue.isEmpty()){
            Node cur=queue.poll();
            int curNodeLevel=levelMap.get(cur);//cur节点所在层
            if(cur.left!=null){
                levelMap.put(cur.left,curLevel+1);
                queue.add(cur.left);
            }
            if(cur.right!=null){
                levelMap.put(cur.right,curLevel+1);
                queue.add(cur.right);
            }
            if(curLevel==curNodeLevel){
                curLevelNodes++;
            }else {
                max=Math.max(max,curLevelNodes);
                curLevel++;
                curLevelNodes=1;
            }
        }
        max=Math.max(max,curLevelNodes);
        return max;
    }

    /**
     * 非map方式实现求最大宽度
     * @param head
     * @return
     */
    /*
                   1
            2              3
         4     5       6       7
      8   9  10 11   12  13  14 15

      1.cur=1 queue:1
        1).nextEnd=null,curEnd=1(head),curLevelNodes=0,max=0
        queue:
        2).nextEnd=2,curEnd=1(head),curLevelNodes=0,max=0
        queue: 2
        3).nextEnd=3,curEnd=1(head),curLevelNodes=0,max=0
        queue: 2 3
        4).nextEnd=3,curEnd=1(head),curLevelNodes=1,max=0
        queue: 2 3
        5).max=1,curLevelNodes=0,curEnd=3
      2.cur=2 queue: 3
        1).nextEnd=4,curEnd=3,curLevelNodes=0,max=1
        queue: 3 4
        2).nextEnd=5,curEnd=3,curLevelNodes=0,max=1
        queue: 3 4 5
        3).nextEnd=5,curEnd=3,curLevelNodes=0,max=1
        queue: 3 4 5
        4).nextEnd=5,curEnd=3,curLevelNodes=1,max=1
        queue: 3 4 5
        5).max=1,curLevelNodes=0,curEnd=3
      3.cur=3 queue: 4 5
        1).nextEnd=5,curEnd=3,curLevelNodes=1,max=1
        queue: 4 5
        2).nextEnd=6,curEnd=3,curLevelNodes=1,max=1
        queue: 4 5 6
        3).nextEnd=7,curEnd=3,curLevelNodes=1,max=1
        queue: 4 5 6 7
        4).nextEnd=3,curEnd=3,curLevelNodes=2,max=1
        queue: 4 5 6 7
        5).max=2,curLevelNodes=0,curEnd=7\

        .
        .
        .
        .



     */
    public static  int maxWidthNoMap(Node head){
        if(head==null){
            return 0;
        }
        Queue<Node> queue = new LinkedList<>();
        Node nextEnd=null;//下一层恶的最右节点
        Node curEnd=head;//当前层最右节点
        queue.add(head);
        int curLevelNodes=0;//当前层的节点数量
        int max=0;//最大节点数
        while (!queue.isEmpty()){
            // 1)
            Node cur=queue.poll();
            // 2)
            if(cur.left!=null){
                queue.add(cur.left);
                nextEnd=cur.left;
            }
            // 3)
            if(cur.right!=null){
                queue.add(cur.right);
                nextEnd=cur.right;
            }
            // 4)
            curLevelNodes++;
            //  5)
            if(cur==curEnd){
                max=Math.max(max,curLevelNodes);
                curLevelNodes=0;
                curEnd=nextEnd;
            }
        }
        return max;
    }









}
